package dp;

public class P322 {
    public int coinChange(int[] coins, int amount) {
        int result = recursion(coins, amount);
        if (result == Integer.MAX_VALUE) {
            return -1;
        } else {
            return result;
        }
    }

    public int dp(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // base
        for (int coin : coins) {
            if (coin <= amount)
                dp[coin] = 1;
        }
        // 状态选择
        for (int i = 1; i <= amount; i++) {
            int minCount = dp[i] == 0 ? Integer.MAX_VALUE : dp[i];
            for (int coin : coins) {
                if (i - coin > 0 && dp[i - coin] != 0) {//还有
                    int total = dp[i - coin] + 1;
                    minCount = Math.min(total, minCount);
                }
            }
            dp[i] = minCount == Integer.MAX_VALUE ? 0 : minCount;
        }
        return dp[amount] == 0 ? -1 : dp[amount];
    }

    /**
     * @param coins
     * @param amount
     * @return 返回Interger.MAX_VALULE为无法处理
     */
    private int recursion(int[] coins, int amount) {

        if (amount == 0) {
            return 0;
        } else if (amount < 0) {
            return -1;
        } else {
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                int count = recursion(coins, amount - coin) + 1;
                if (count >= 1) {
                    min = Math.min(min, count);
                }
            }
            return min;
        }
    }

    public static void main(String[] args) {
        int result = new P322().dp(new int[]{2}, 3);
        System.out.println(result);
    }
}
